Paper 2020/1160

Characterizing Deterministic-Prover Zero Knowledge

Nir Bitansky and Arka Rai Choudhuri

Abstract

Randomness is typically thought to be essential for zero knowledge protocols. Following this intuition, Goldreich and Oren (Journal of Cryptology 94) proved that auxiliary-input zero knowledge cannot be achieved with a deterministic prover. On the other hand, positive results are only known in the honest-verifier setting, or when the prover is given at least a restricted source of entropy. We prove that removing (or just bounding) the verifier's auxiliary input, deterministic-prover zero knowledge becomes feasible: - Assuming non-interactive witness-indistinguishable proofs and subexponential indistinguishability obfuscation and one-way functions, we construct deterministic-prover zero-knowledge arguments for $\mathsf{NP}\cap \mathsf{coNP}$ against verifiers with bounded non-uniform auxiliary input. - Assuming also keyless hash functions that are collision-resistant against bounded-auxiliary-input quasipolynomial-time attackers, we construct similar arguments for all of $\mathsf{NP}$. Together with the result of Goldreich and Oren, this characterizes when deterministic-prover zero knowledge is feasible. We also demonstrate the necessity of strong assumptions, by showing that deterministic prover zero knowledge arguments for a given language imply witness encryption for that language. We further prove that such arguments can always be collapsed to two messages and be made laconic. These implications rely on a more general connection with the notion of predictable arguments by Faonio, Nielsen, and Venturi (PKC 17).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2020
Keywords
zero knowledge
Contact author(s)
nirbitan @ tau ac il
achoud @ cs jhu edu
History
2020-09-25: received
Short URL
https://ia.cr/2020/1160
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1160,
      author = {Nir Bitansky and Arka Rai Choudhuri},
      title = {Characterizing Deterministic-Prover Zero Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1160},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1160}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.